[競プロ][Python] ユニークな文字からなる最長の部分文字列の長さを取得する

#Python

masuwo3

2019.10.07

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

本記事では「ユニークな文字からなる最長の部分文字列の長さを取得する」プログラムの効率的な書き方について解説します。
問題・解説についてはleetcodeの3. Longest Substring Without Repeating Charactersを参考にしています。

問題

与えられた文字列に対して、それぞれの文字を繰り返さない最長の部分文字列の長さを求めなさい。

例えば、abcabcbb が与えられた場合は、abcが対象の部分文字列に該当し、その長さ3を返すことが正解です。

入力文字列と部分文字列の例を以下の表にまとめます。

入力文字列	部分文字列	長さ
"abcabcbb"	"abc"	3
"bbbbb"	"b"	1
"pwwkew"	"wke"	3

解法1. Blute Force

ひとまず効率を考慮せず、愚直に計算することを考えます。

長さnを持つ文字列sに対して、0≦i<j≦nとなる部分文字列s_i_jを全て列挙し、それぞれについてユニークな文字列で構成されているかを判定したのち、最長の部分文字列の長さを求めます。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ret = 0
        for i in range(len(s)):
            for j in range(i, len(s) + 1):
                subs = s[i:j]  # 部分文字列
                if len(set(subs)) == len(subs):
                    ret = len(subs) if ret < len(subs) else ret
        return ret

forループが2重にネストされていることから、長い文字列の場合には計算にかなり時間がかかることが想像できます。実際、leetcode上で実行した場合Time Limit Exceededが返され、結果は失敗となります。長さnのユニークな文字列が与えられた場合、(set()の計算量がO(n)だと仮定すると)全体の計算量はO(n^3)です。

ひとまずこのアプローチのまま処理の効率化を試みます。

ある時点で部分文字列がユニークでないと判定された場合、そこから部分文字列の末尾を伸ばしても常に判定は失敗するため、一度失敗した時点で処理を打ち切れば無駄な計算を省くことが出来ます。

また、より長い部分文字列の探索が目的なので、iを更新する際にはjをその時点での最長の長さを加えた地点をスタートラインとすることで、短い部分文字列の判定を省けます。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ret = 0
        for i in range(len(s)):
            for j in range(i + ret, len(s) + 1):  # jの開始地点にその時点での最長を加える
                subs = s[i:j]
                if len(set(subs)) == len(subs):
                    ret = len(subs) if ret < len(subs) else ret
                    continue
                break  # 判定に失敗すればjの更新をスキップ
        return ret

この改良を加えることでleetcodeのテストはパスすることが出来ます。しかし、はじめに話した通りforが二重にループしていることやset(subs)の中でも文字列を走査していることが想像できるため、やはり計算効率はあまり良くなさそうです。

解法2. Sliding Window

上記のアプローチでは、1文字ずつ範囲をずらして探索していましたが、部分文字列について都度set()を行いユニークかどうかを判定していました。これは非効率なので増加・減少した範囲のみを焦点に判定を行うように改善します。

具体的には、部分文字列に対してユニークな文字を持つwindowを導入し、以下のように処理を進めます。

s[j]がwindowに含まれていない場合、windowに含め、jを進める
s[j]がwindowに含まれる場合、s[i]をwindowから除き、iを進める
i,jがnを超過するまで1. 2.を繰り返す

jが更新される際、[i,j)の範囲において部分文字列s_i_jのユニーク性は常に保たれており、効率的に部分文字列を探索することが出来ます。当然windowのサイズは常に部分文字列の最大長を越えることがないため、jが更新された段階でのwindowのサイズを常に監視し、その最大値を返すことで求めたい長さを得ることが出来ます。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = set()
        max_size = 0
        i, j, n = 0, 0, len(s)
        while i < n and j < n:
            if s[j] not in window:
                # windowに含まれていない場合、windowに含め、jを進める
                window.add(s[j])
                max_size = max(len(window), max_size)
                j += 1
            else:
                # windowに含まれる場合、s[i]をwindowから除き、iを進める
                window.discard(s[i])
                i += 1
        return max_size

このアプローチを取ることで、i, jが最もスライドした場合であっても計算量はO(2n)≒O(n)程度に抑えることが出来ます。

解法3. Sliding Window Optimized

解法2.ではs[j]がwindow内にすでに存在していれば、window内から無くなるまでiを一つずつ先に進めていました。各文字の位置を事前に記憶しておけば、iの更新を効率化出来ます。

このアプローチでは、s[j]がwindow内にあった場合、[i,j)内に同じ文字が現れた最新の位置を参照し、iをその一つ先に更新します。

各文字の最新の位置情報は辞書型の配列に記憶すれば良さそうです。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = dict()
        max_size = 0
        i, j, n = 0, 0, len(s)
        while i < n and j < n:
            if s[j] in window:
                i = max(i, window[s[j]] + 1)
            window[s[j]] = j
            max_size = max(max_size, j - i + 1)
            j += 1
        return max_size

明言はされていませんが、文字列はasciiで構成されているらしいので、サイズ256の配列でも代用は可能です。この場合、初期値を-1に設定しておけばif分岐を一つなくすことが出来ます。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = [-1] * 256
        max_size = 0
        i, j, n = 0, 0, len(s)
        while i < n and j < n:
            sj = ord(s[j])
            i = max(i, window[sj] + 1)
            window[sj] = j
            max_size = max(max_size, j - i + 1)
            j += 1
        return max_size